#include <vector>
#include <random>
using namespace std;
/*
 * @lc app=leetcode.cn id=162 lang=cpp
 *
 * [162] 寻找峰值
 */

// @lc code=start
class Solution {
public:
    // log n实现
    // int findPeakElement(vector<int>& nums) {
    //     // 爬坡法
    //     int n = nums.size();
    //     auto get = [&](int i) -> pair<int, int> {
    //         if (i == -1 || i == n) {
    //             return {0, 0};
    //         }
    //         return {1, nums[i]};
    //     };
    //     int idx = rand() % n;
    //     while (!(get(idx) > get(idx + 1) && get(idx) > get(idx - 1))) {
    //         if (get(idx) < get(idx + 1)) idx++;
    //         else idx--;
    //     }
    //     return idx;
    // }

    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1, n = nums.size();
        auto get = [&](int i) -> pair<int, int> {
            if (i == -1 || i == n) return {0, 0};
            return {1, nums[i]};
        };
        // [ ]
        while (l < r) {
            int middle = (l + r) / 2;
            if (get(middle) > get(middle + 1) && get(middle) > get(middle - 1)) return middle;
            else if (get(middle + 1) > get(middle)) l = middle + 1;
            else if (get(middle) < get(middle - 1)) r = middle - 1;
        }
        return l;
    }


};
// @lc code=end

